/*
 * Copyright (c) 2011 Robert Kirchgessner <rkirchge@gmail.com>
 *                    Carlo Pascoe <carlo.pascoe@gmail.com>
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>

#include "debug.h"
#include "graph.h"

#define COORD(X,Y,N) (X*N + Y)

static struct vertice *_get_free_vertice();
static struct edge *_get_free_edge();
static struct vertice *
_get_free_vertice()
{
  return (struct vertice *)malloc(sizeof(struct vertice));
}

static struct edge *
_get_free_edge()
{
  return (struct edge *)malloc(sizeof(struct edge));
}

void
graph_init(struct graph *g)
{
  g->size = 0;
  g->edges = 0;
  LIST_INIT(&g->vertices);
}

void 
graph_cleanup(struct graph *g)
{
  struct vertice *v, *nv;
  struct edge *e, *ne;
  v = LIST_FIRST(&g->vertices);

  debug("Cleaning up graph..\n", NULL);
  while(v) {
    nv = LIST_NEXT(v, next);
    e = LIST_FIRST(&v->edges);

    //Delete all edge entries
    while(e) {
      ne = LIST_NEXT(e, next);
      free(e);
      e = ne;
    }
    free(v);

    v = nv;
  }

}

struct vertice *
graph_insert_vertex(struct graph *g, uint32_t id)
{
  struct vertice *v, *next, *new;

  debug("Trying to add vertex: %d\n", id);

  v = LIST_FIRST(&g->vertices);

  if(v == NULL || id < v->id) {
    debug("Inserting new head: %d\n", id);
    new = _get_free_vertice();
    LIST_INIT(&new->edges);
    new->id = id;
    new->degree = 0;
    LIST_INSERT_HEAD(&g->vertices, new, next);
    g->size++;
    return new;
  }

  //Insert a vertex sorted by ID (so searching the vertex list can be faster)
  while(v) {
    next = LIST_NEXT(v, next);
    if(id == v->id) {
      debug("Duplicate ID Detected -- Not inserting %d\n", id);
      return v;
    }
    else if(next == NULL || (id > v->id && id < next->id)) {
      break;
    }
    else {
      v = next;
    }
  }

  new = _get_free_vertice();
  LIST_INIT(&new->edges);
  new->id = id;
  new->degree = 0;
  debug("Inserting after element: %d -> %d\n", v->id, id);
  LIST_INSERT_AFTER(v, new, next);
  g->size++;
  return new;
}

void
graph_print(struct graph *g)
{
  struct vertice *current;
  struct edge *edge;

  LIST_FOREACH(current, &g->vertices, next) {
    printf("Vertice: %d\n", current->id);
    printf("Edge list: \n");

    LIST_FOREACH(edge, &current->edges, next) {
      printf("%d -- %d\n", current->id, edge->v->id);
    }
  }
}

void
graph_insert_edge(struct graph *g, uint32_t id0, uint32_t id1)
{
  struct edge *edge;
  struct vertice *v1, *v2;
  debug("Inserting edge between: %d -- %d\n", id0, id1);
  v1 = graph_insert_vertex(g, id0);
  v2 = graph_insert_vertex(g, id1);

  //Iterate over existing edge list for v1
  LIST_FOREACH(edge, &v1->edges, next) {
    if(edge->v == v2) {
      debug("Duplicate edge detected, not adding. %d -- %d\n", v1->id, v2->id);
      return;
    }
  }

  v1->degree++;
  edge = _get_free_edge();
  edge->v = v2;
  LIST_INSERT_HEAD(&v1->edges, edge, next);

  v2->degree++;
  edge = _get_free_edge();
  edge->v = v1;
  LIST_INSERT_HEAD(&v2->edges, edge, next);

  g->edges++;
}


/**
 * @brief Write dotty graph
 * @param fname File to write
 * @param g Pointer to a graph structure
 */
void 
graph_write_dotty(const char *fname, struct graph *g)
{
  uint32_t *index_table;
  struct vertice *vertex;
  index_table = (uint32_t *)malloc(g->size*sizeof(uint32_t));
  int index = 0;
  LIST_FOREACH(vertex, &g->vertices, next){
    index_table[index++] = vertex->id;
  }

  uint32_t *adj = malloc(g->size * g->size * sizeof(uint32_t));
  graph_make_adjacency(g, adj);
  
  //Write node list
  FILE *fp = fopen(fname, "w");
  if(!fp) {
    fprintf(stderr, "Could not open file for writing: %s\n", fname);
    free(index_table);
    return;
  }

  fprintf(fp, "graph g {\n");

  if(g->edges == 0) {
    fprintf(fp, "0");
  } else {

  //Write nodes
  #if 0
  for(index=0; index<g->size; index++) {
    fprintf(fp, "%d [label = \"%d\"]\n", index_table[index], index_table[index]);
  } 

  fprintf(fp, "\n\n");
  #endif
  //Write Edges
  int x,y;

  for(x=0; x<g->size; x++) {
    for(y=x; y<g->size; y++) {
      if(adj[COORD(x,y,g->size)]) {
        fprintf(fp, "%d -- %d\n", index_table[x], index_table[y]);
      }
    }
  }
  }
  fprintf(fp, "}\n\n");
  fclose(fp);
  free(index_table);
  free(adj);
}

static int 
find_int(uint32_t ele, uint32_t* array, uint32_t size)
{
  int low, high, pivot;

  low = 0;
  high = size-1;

  while(1) {
    pivot = (high+low)/2;
    if(array[pivot] == ele) {
      return pivot;
    }
    else if(array[pivot] < ele) {
      low = pivot+1;
    }
    else if(array[pivot] > ele) {
      high = pivot-1;
    }
    
    if(high < low) {
      return -1;
    }
  }
}

/**
 * @brief Make the adjacency matrix for a graph
 * @param g Pointer to a graph structure
 * @param adj Pointer to a matrix with enough size to store adjacency matrix
 */
void 
graph_make_adjacency(struct graph *g, uint32_t *adj)
{
  uint32_t *index_table;
  index_table = (uint32_t *)malloc(g->size*sizeof(uint32_t));
  memset(adj, 0, g->size*g->size*sizeof(uint32_t));

  //Build index table
  struct vertice *vertex;
  struct edge *edge;

  //Generate the lookup table for node ids->index
  int index = 0;
  LIST_FOREACH(vertex, &g->vertices, next){
    index_table[index++] = vertex->id;
  }

  //Generate the adjacency matrix
  int x, y;
  LIST_FOREACH(vertex, &g->vertices, next){
    x = find_int(vertex->id, index_table, g->size);
    LIST_FOREACH(edge, &vertex->edges, next) {
      y = find_int(edge->v->id, index_table, g->size);
      adj[COORD(x,y,g->size)] = 1;
    }
  }
  
  free(index_table);
}

/*
 */
uint32_t
graph_get_degree(struct vertice *v)
{
  struct edge *e;
  uint32_t degree = 0;
  
  LIST_FOREACH(e, &v->edges, next) {
    degree++;
  }

  return degree;
}

uint32_t 
graph_is_adjacent(struct vertice *v0, struct vertice *v1)
{
  struct edge *e;

  LIST_FOREACH(e, &v0->edges, next) {
    if(e->v->id == v1->id) {
      return 1;
    }
  }
  return 0;
}

void
graph_copy(struct graph *g0, uint32_t *adj, struct graph *g1)
{
  struct vertice *v0, **v_list, *v_new, *v_last;
  struct edge *e;
  uint32_t *orig_adj;

  if(adj == NULL) {
    orig_adj = (uint32_t*)malloc(g0->size*g0->size*sizeof(uint32_t));
    assert(orig_adj != NULL);
    //Generate the adjacency matrix
    graph_make_adjacency(g0, orig_adj);
  }
  else {
    orig_adj = adj;
  }

  //Store pointers to the new vertices for fast access;
  v_list = (struct vertice **)malloc(g0->size * sizeof(struct vertice *));
  assert(v_list != NULL);

  v0 = LIST_FIRST(&g0->vertices);
  uint32_t x, y;

  x=0;
  v_last = NULL;
  LIST_FOREACH(v0, &g0->vertices, next) {
    v_new = _get_free_vertice();
    //Insert new vertice in the linear lookup array
    v_list[x++] = v_new;
    LIST_INIT(&v_new->edges);
    
    //Copy original node id/degree
    v_new->id = v0->id;
    v_new->degree = v0->degree;

    //Insert the new vertice in the graph
    if(v_last == NULL) {
      LIST_INSERT_HEAD(&g1->vertices, v_new, next);
    }
    else {
      LIST_INSERT_AFTER(v_last, v_new, next);
    }
    v_last = v_new;
  }

  //Iterate over the original adj matrix to build the new graph
  for(x=0; x<g0->size; x++) {
    for(y=x; y<g0->size; y++) {
      if(orig_adj[COORD(x,y,g0->size)] == 1) {
        e = _get_free_edge(); 
	e->v = v_list[y];
        LIST_INSERT_HEAD(&v_list[x]->edges, e, next);
        
	e = _get_free_edge(); 
	e->v = v_list[x];
        LIST_INSERT_HEAD(&v_list[y]->edges, e, next);
      }
    }
  }

  g1->size = g0->size;
  g1->edges = g0->edges;
  free(v_list);

  if(adj == NULL) {
    free(orig_adj);
  }

}

void
graph_from_adj(uint32_t *adj, uint32_t size, struct graph *g)
{
  struct vertice *v, *vlast, **v_list;
  uint32_t index;

  v_list = (struct vertice **)malloc(size * sizeof(struct vertice *));

  //Efficiently build vertice list
  vlast = NULL;
  for(index=0; index<size; index++) {
    v = _get_free_vertice();
    v_list[index] = v;
    assert(v!=NULL);
    v->id = index;
    v->degree = 0;
    LIST_INIT(&v->edges);

    if(vlast == NULL) {
      LIST_INSERT_HEAD(&g->vertices, v, next);
      g->size ++;
    }
    else {
      LIST_INSERT_AFTER(vlast, v, next);
      g->size++;
    }

    vlast = v;
  }
  
  //Build edge list from adjacency matrix
  uint32_t x, y;
  struct edge *e;

 for(x=0; x<size; x++) {
   for(y=x; y<size; y++) {
     if(adj[COORD(x,y,size)] == 1) {
       g->edges++;
       e = _get_free_edge();
       e->v = v_list[y];
       LIST_INSERT_HEAD(&v_list[x]->edges, e, next);
       v_list[x]->degree++;

       e = _get_free_edge();
       e->v = v_list[x];
       LIST_INSERT_HEAD(&v_list[y]->edges, e, next);
       v_list[y]->degree++;
     }
   }
 }

 free(v_list);
}

uint32_t
graph_isomorphic(struct graph *g0, struct graph *g1)
{
  uint32_t *adj0, *adj1;
  if(g0->size != g1->size) {
    return 0;
  }

  adj0 = (uint32_t *)malloc(g0->size*g0->size*sizeof(uint32_t));
  assert(adj0 != NULL);
  memset(adj0, 0, g0->size*g0->size*sizeof(uint32_t));

  adj1 = (uint32_t *)malloc(g0->size*g0->size*sizeof(uint32_t));
  assert(adj1 != NULL);
  memset(adj1, 0, g0->size*g0->size*sizeof(uint32_t));

  graph_make_adjacency(g0, adj0);
  graph_make_adjacency(g1, adj1);

  uint32_t x, y;
  for(x=0; x<g0->size; x++) {
    for(y=x; y<g0->size; y++) {
      if(adj0[COORD(x,y,g0->size)] != adj1[COORD(x,y,g0->size)]) {
        free(adj0);
	free(adj1);
	return 0; 
      }
    }
  }

  free(adj0);
  free(adj1);
  return 1;
}

uint32_t
graph_from_file(const char *fname, struct graph *g)
{
    uint32_t nvertex, i, j;

    FILE *fp = fopen(fname, "r");
    if (!fp)
    {
        fprintf(stderr, "Could not open file: %s.\n", fname);
        exit(-1);
    }

    fscanf(fp, "%d\n", &nvertex);
    while (!feof(fp))
    {
        fscanf(fp, "%d %d\n", &i, &j);
        graph_insert_edge(g, i, j);
    }

    if (g->size != nvertex)
    {
        fprintf(stderr, "File states %d vertices, but found %d!\n", nvertex, g->size);
        exit(-1);
    }

    fclose(fp);
    return nvertex;
}

#ifdef __TEST__
#include <sys/time.h>
double timerval() 
{
  struct timeval st;
  gettimeofday(&st, NULL);
  return (st.tv_sec + st.tv_usec*1e-6);
}

int
main(int argc, char *argv[])
{
  struct graph g;
  graph_init(&g);
  int k;
  double start = timerval();
  for(k=0; k<100000; k++) {
    graph_insert_edge(&g, k, k+1);
  }
  double end = timerval();
  printf("Total time: %lf\n", end-start);
  usleep(10000000);
  graph_cleanup(&g);
  usleep(10000000);
  return 0;
}

#endif

